package com.example.linked.skiplist;

public class SkiplistNoIndex {
    final int HEAD_VALUE = -1; // 链表头节点的值

    private Node head;

    // 跳表层级数
    private int levels;
    // 跳表节点数(不包括索引层)
    int size;

    public SkiplistNoIndex() {
        // 对跳表进行初始化，此时跳表中只有一个头结点,层级也只有一级
//        head = HEAD;
        head = new Node(HEAD_VALUE);
        this.levels = 1;
        this.size = 0;
    }

    /**
     * 向跳表添加一个数据(不考虑添加索引层)
     * 1.遍历跳表，找到合适的插入位置（原链表中 >= num 的最小节点前）
     * 逐层遍历链表，如果在某层遇到了大于num的节点，则说明找到了位置
     * 2.将节点插入
     *
     * @param num
     */
    public void add(int num) {
        Node cur = head;
        // 1. 遍历跳表，找到合适的插入位置
        // 外层循环控制层级的切换，内存循环控制每层的遍历
        while (cur != null) {
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }
            // 退出内层循环说明cur右节点值大于或者等于 num
            if (cur.down == null) {
                break;
            }
            cur = cur.down;
        }
        // 退出双重循环时，一定是移动到了原链表层的合适位置，
        // 且cur一定是位于要插入位置的前一个节点上

        // 2. 将数据插入原链表层的链表中
        Node newNode = new Node(num, cur.right, null);
        cur.right = newNode;
        ++size;
    }

    /**
     * 查询跳表中是否有目标值
     * <p>
     * 逐层遍历链表，如果在某层遇到了等于target的节点，则说明存在
     *
     * @param target
     * @return
     */
    public boolean search(int target) {
        Node cur = head;
        // 外层循环控制层级的切换，内存循环控制每层的遍历
        while (cur != null) {
            // 同一层级，cur右节点值小于target时依次向右移动cur指针
            while (cur.right != null && cur.right.val < target) {
                cur = cur.right;
            }
            // 退出内层循环说明cur右节点值大于或者等于 target
            // 等于的情况，直接返回
            if (cur.right != null && cur.right.val == target) {
                return true;
            }
            // 大于的情况则需要移动到下一层，然后继续
            cur = cur.down;
        }
        // 遍历完了跳表，没有数据返回false
        return false;
    }

    /**
     * 删除指定的节点
     * 1.遍历跳表，找到和要删除元素相同的节点
     * 2.将节点删除
     *
     * @param num
     * @return
     */
    public boolean erase(int num) {
        boolean flag = false;
        Node cur = head;
        // 1. 遍历跳表，找到合适的插入位置
        // 外层循环控制层级的切换，内存循环控制每层的遍历
        while (cur != null) { //cur == null 说明到了原链表层

            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }

            Node targetNode = cur.right;
            // 找到了相同的元素，从当前层链表中删除该元素
            if (targetNode != null && targetNode.val == num) {
                cur.right = targetNode.right;
                targetNode.right = null;
                --size;
                flag = true;
            }
            // 跳到下一层去
            cur = cur.down;
        }
        if (flag) {
            --size;
        }
        // 遍历完了整个跳表，说明没有该元素
        return flag;
    }
}
